/**
 * Created by L.jp
 * Description:输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，
 * 所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的
 * User: 86189
 * Date: 2022-05-16
 * Time: 19:30
 */
//class ListNode {
//    int val;
//    ListNode next = null;
//
//    ListNode(int val) {
//        this.val = val;
//    }
//}
public class Sloution {
    public int getLen(ListNode head){
        ListNode cur=head;
        int n=0;
        while (cur!=null){
            cur=cur.next;
            n++;
        }
        return n;
    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        /*使用双指针求出各自的长度，取差值n，长的链表先走n步，然后一起走，相遇时既为第一个公共节点*/
       int len1=getLen(pHead1);
       int len2=getLen(pHead2);
       if(len1>=len2){
           int n=len1-len2;
            while (n>0){
                pHead1=pHead1.next;
                n--;
            }
            while (pHead1!=null && pHead2!=null && pHead1!=pHead2){
                pHead1= pHead1.next;
                pHead2=pHead2.next;
            }
        }else{
           int n=len2-len1;
            while (n>0){
                pHead2=pHead2.next;
                n--;
            }
            while (pHead1!=null && pHead2!=null && pHead1!=pHead2){
                pHead1= pHead1.next;
                pHead2=pHead2.next;
            }
        }
        return pHead1;
    }
}
